package org.skywork.top.core.algorithm.num;

import java.util.HashMap;
import java.util.Map;

/**
 * 爬楼梯
 */
public class no_70 {


    /**
     * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
     * <p>
     * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
     */

    static Map<Integer, Integer> map = new HashMap<>();

    public static int climbStairs(int n) {

        /**
         * 示例 1：
         * 输入：n = 2
         * 输出：2
         * 解释：有两种方法可以爬到楼顶。
         * 1. 1 阶 + 1 阶
         * 2. 2 阶
         *
         * 示例 2：
         *
         * 输入：n = 3
         * 输出：3
         * 解释：有三种方法可以爬到楼顶。
         * 1. 1 阶 + 1 阶 + 1 阶
         * 2. 1 阶 + 2 阶
         * 3. 2 阶 + 1 阶
         */
        if(map.get(n) != null){
            return map.get(n);
        }

        if (n == 1) {
            return 1;
        }
        if(n == 2){
            return 2;
        }
        if(n == 3){
            return 3;
        }
        if(n == 4){
            return 5;
        }
        if(n == 5){
          return 8;
        }
        if(n == 6){
            return 13;
        }
        if(n == 7){
            return 21;
        }
        if(n == 8){
            return 34;
        }
        if(n == 9){
            return 55;
        }
        if(n == 10){
            return 89;
        }
        int result = climbStairs(n - 1) + climbStairs(n - 2);
        map.put(n, result);
        return result;
    }

    public static void main(String[] args) {
        int num = climbStairs(45);
        System.out.println(num);
    }
}
